public class BinaryTree {
    static class  TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode root;//将来这个引用 指向的就是根节点

    public TreeNode createNode(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');


        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return  A;
    }


    //前序遍历
    public void preOrder(TreeNode root){//递归

        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);

    }

    //后续遍历
    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //计算节点的个数
    int size = 0;
    public int nodeSize(TreeNode root){
        if(root == null){
            return 0;
        }
        size++;
        nodeSize(root.left);
        nodeSize(root.right);
        return size;
    }

    public int nodeSize2(TreeNode root){//子问题方法：左树 加 右数的节点 加1 就是总结点
        if(root == null){
            return 0;
        }
        return nodeSize2(root.left) + nodeSize2(root.right) + 1;
    }

    //求叶子节点的个数
    int leafSize = 0;
    public void getLeafSize(TreeNode root ){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            leafSize++;
        }
        getLeafSize(root.left);
        getLeafSize(root.right);
    }

    public int getLeafSize2(TreeNode root ){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right) ;
    }

    //第k层有多少个节点
    public int getLevelNodeCount(TreeNode root,int k){//root这棵树第k层数 = root.left的k-1层数 + root.right k-1的层数
        if(root == null){
            return 0;
        }
        if(k == 1){       //此时到达了第k层（上下层始终差1    递减1  ）
            return 1;
        }
        return getLevelNodeCount(root.left,k-1) + getLevelNodeCount(root.right,k-1);
    }

    //====================================================================
    //求树的高度：左树的高度 和 右树的高度的最大值加1（关键思想）大转小问题
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight > rightHeight ? leftHeight +1 :rightHeight +1); 
    }

    //==================================================================//
    //查找关键字key是否在树中
    public boolean find(TreeNode root,char key){
        if(root == null){//判断树是否为空
            return  false;
        }

        if(root.val == key){//判断值是否为key
            return true;
        }
        boolean leftVal = find(root.left,key);//迭代左树
        if(leftVal == true){
            return true;
        }
        boolean rightVal = find(root.right,key);//迭代右树
        if(rightVal == true){
            return true;
        }

        return false;//走到这一步说明树中的节点 找不到key
    }
}
